  /*fig7-10*/
template <typename Comparable>
void heapsort( vector<Comparable> & a )
{
	for( int i = a.size()/2; i >= 0; i-- ) /*buildHeap*/ //将数组调成成为一个从大到小排序的有序数组,即建立Heap
		percDown( a, i, a.size() );  
	for( int j = a.size()-1; j>0; j-- )  /*deleteMin*/
	{
		swap( a[0], a[j] ); /*把现在数组中最大的数挪到最后肚饿空出来的位子上*/
		percDown( a, 0, j ); //下滤将最大的数再顶上来
	}
}


inline int leftChild( int i )   //维护程序的可读性，不然每次想取左孩子都要写一个并不是非常直观的公式
{
    return 2 * i + 1;
}


template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n )  //下滤，i是开始下滤的位置，n是heap的长度，用来限制处理的范围，防止误处理到已经移出数组的数据。
{
    int child;
    Comparable tmp; //用于腾出a[i]的位置的同时保存a[i]的值，做到只调整a[i]的subHeap。故建立数组的时候需要把a[0]的位置空出来，方便调整整个数组。

    for( tmp = std::move( a[ i ] ); leftChild( i ) < n; i = child ) 
    {
        child = leftChild( i ); //一定有左孩子，不一定有右孩子，所以是等于leftChild
        if( child != n - 1 && a[ child ] < a[ child + 1 ] )//如果右孩子比左孩子大的话，则下滤时交换父亲和右儿子。同时限制child的位置没有超出当前数组，防止误处理已经被处理过的数据。
            ++child;
        if( tmp < a[ child ] )         //如果这个点的key比它的孩子小，就是不符合从大到小的顺序，需要交换结点和孩子
            a[ i ] = std::move( a[ child ] );  
        else                                  //key比孩子大，即程序已经走到堆的=0的那一层，孩子是空的。故break跳出循环
            break;
    }
    a[ i ] = std::move( tmp );   //恢复a[i]的值


/*fig 7-11*/

template <typename Comparable>
void mergeSort( vector<Comparable> & a )
{
    vector<Comparable> tmpArray( a.size( ) ); //用于保存归并结果的数组

    mergeSort( a, tmpArray, 0, a.size( ) - 1 );
}


template <typename Comparable>
void mergeSort( vector<Comparable> & a,
                vector<Comparable> & tmpArray, int left, int right ) //将一个数组递归的拆分左右，分治处理。
{
    if( left < right )
    {
        int center = ( left + right ) / 2;
        mergeSort( a, tmpArray, left, center ); 
        mergeSort( a, tmpArray, center + 1, right ); 
        //将数组分成两半，单独对两边排序获得有序数组。
        //传入的（ left,center ）和( center+1,right )分别是左右两边数组的起和始
        //不停地拆分到最后会获得分别只有一个数字的左部和右部，可以视为是已经排好序了的数组，然后调用merge（）
        
        merge( a, tmpArray, left, center + 1, right );
        //将两边的有序数组归并，获得最终的有序数组。
        //传入center+1用来确定右部开始的地方
    }
}



/*fig 7-12*/
template <typename Comparable>
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray,
            int leftPos, int rightPos, int rightEnd )
{
    int leftEnd = rightPos - 1;           //记录左部结束的地方，之后rightPos就可以用于循环取右部中的元素。
	int tmpPos = leftPos;                 //tmpPos使得给tmpArray中复制的时候元素的位置和排序完之后对应的在中的位置一样，可以化简之后的把tmpArray中的元素再移动回a的程序
    int numElements = rightEnd - leftPos + 1;   //方便确定把tmpArray中的元素再移动回a的程序的运行次数

    // 主循环，比较左右两边中现在的计数器所在位置的元素大小，将较小的移动到tmpArray。
    // 使用移动而不是复制，这样子总的程序就是需要一个数组的临时储存空间。否则每次递归都需要声明一个新的数组，非常占用内存
    while( leftPos <= leftEnd && rightPos <= rightEnd )    // 验证数组还没有走到头
		if( a[ leftPos ] <= a[ rightPos ] )                 
            tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
        else
            tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );

    while( leftPos <= leftEnd )    // 如果一部分结束后，剩下的数组是左部，则把左部剩下的元素全部移动到temArray之中
        tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );

    while( rightPos <= rightEnd )  // 同理，如果剩下的是右部，则把右部中剩下的元素全部移动到temArray之中
        tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );

    // 把temArray中的元素移动回a
    for( int i = 0; i < numElements; ++i, --rightEnd )
        a[ rightEnd ] = std::move( tmpArray[ rightEnd ] );
}

/*fig 7-14*/
template <typename Comparable>
void quicksort( vector<Comparable> & a ) //一个平平无奇的启动器
{
    quicksort( a, 0, a.size( ) - 1 );  //把输入在排序中不被关心的size-1，0的活干了，用户只需要输入a，比较符合逻辑。
}
/*fig 7-15*/
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right )//将数组中头尾和中间的三个元素排序，选出枢纽元。同时把三个中最小的放在数组最左边正确的位置，最大的放在右边正确的位置。
{
    int center = ( left + right ) / 2;
    
    if( a[ center ] < a[ left ] )
        std::swap( a[ left ], a[ center ] );
    if( a[ right ] < a[ left ] )
        std::swap( a[ left ], a[ right ] );
    if( a[ right ] < a[ center ] )
        std::swap( a[ center ], a[ right ] );

        // 把枢纽点放到right-1的位置，给i提供了一个警戒标记。
    std::swap( a[ center ], a[ right - 1 ] );
    return a[ right - 1 ];
}


/*fig-7.16*/
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right )
{
    if( left + 10 <= right ) //防止对小数组使用快速排序，提高程序的运行效率
    {
        const Comparable & pivot = median3( a, left, right );//三数中值分割

            // 分区
        int i = left, j = right - 1;  
        for( ; ; )    
        {
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                std::swap( a[ i ], a[ j ] );
            else
                break;
        }

        std::swap( a[ i ], a[ right - 1 ] );  // 重新设置枢纽元

        quicksort( a, left, i - 1 );     // 给小于枢纽元的元素排序
        quicksort( a, i + 1, right );    // 给大于枢纽元的数组排序
    }
    else  //用插入排序处理小数组，提高程序运行效率
        insertionSort( a, left, right );
}



/*fig7.17*/
int i = left, j = right - 1;
        for( ; ; )
        {
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                std::swap( a[ i ], a[ j ] );  //如果a[i]=a[j]=pivot，则这里会产生一个无限循环。这是一个错误的写法。
            else
                break;
        }


